import java.util.*;
public class test {
    //leetcode 496.下一个更大元素Ⅰ
    class Solution {
        //哈希表 + 单调栈
        public int[] nextGreaterElement(int[] nums1, int[] nums2) {
            HashMap<Integer,Integer> map = new HashMap<>();
            Deque<Integer> deque = new ArrayDeque<>();
            int[] nums = new int[nums1.length];
            Arrays.fill(nums,-1);
            for(int i = 0;i < nums1.length;i++){
                map.put(nums1[i],i);
            }
            for(int i = 0;i < nums2.length;i++){
                while(!deque.isEmpty() && nums2[i] > deque.peek() && map.containsKey(deque.peek())){
                    int num = deque.peek();
                    deque.pop();
                    nums[map.get(num)] = nums2[i];
                }
                deque.push(nums2[i]);
            }
            return nums;
        }
    }
    //leetcode 1576.替换所有的问号
    class Solution {
        public String modifyString(String s) {
            char[] arr = s.toCharArray();
            int len = arr.length;
            for(int i = 0;i < len;i++){
                if(arr[i] == '?'){
                    for(char c = 'a';c <= 'z';c++){
                        if((i == 0 || arr[i - 1] != c) && (i == len - 1 || arr[i + 1] != c)){
                            arr[i] = c;
                            break;
                        }
                    }
                }
            }
            return String.valueOf(arr);
        }
    }
    //leetcode 495.提莫攻击
    class Solution {
        public int findPoisonedDuration(int[] timeSeries, int duration) {
            int sum = duration;
            int end = timeSeries[0] + duration;
            for(int i = 1;i < timeSeries.length;i++){
                if(timeSeries[i] <= end){
                    sum += (timeSeries[i] - timeSeries[i - 1]);
                }else {
                    sum += duration;
                }
                end = timeSeries[i] + duration;
            }
            return sum;
        }
    }
    //leetcode 6.Z字形变换
    class Solution {
        public String convert(String s, int numRows) {
            if (numRows == 1) {
                return s;
            }
            int len = s.length();
            char[] c = new char[len];
            int index = 0;
            int n = numRows * 2 - 2;
            for (int i = 0; i < numRows; i++) {
                // 第一列和最后一列
                if (i == 0 || i == numRows - 1) {
                    for (int k = i; k < len; k += n) {
                        c[index++] = s.charAt(k);
                    }
                } else {
                    // 第k列
                    for (int k = i, m = n - i; k < len || m < len; k += n, m += n) {
                        c[index++] = s.charAt(k);
                        if (m < len) {
                            c[index++] = s.charAt(m);
                        }
                    }
                }
            }
            return new String(c);
        }
    }
}
